#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef char BTDataType;

typedef struct BinaryTreeNode
{
    BTDataType val;
    struct BinaryTreeNode *left;
    struct BinaryTreeNode *right;

} BTNode;
typedef BTNode *QDatatype;

typedef struct QueueNode
{
    QDatatype val;
    struct QueueNode *next;
} QNode;
typedef struct Queue
{
    QNode *phead;
    QNode *ptail;
    int size;
} Queue;

// 队列的初始化
void QueueInit(Queue *pq);
// 队列的销毁
void QueueDestroy(Queue *pq);

// 入队列
void QueuePush(Queue *pq, QDatatype x);
// 出队列
void QueuePop(Queue *pq);

// 队头元素
QDatatype QueueFront(Queue *pq);
// 队尾元素
QDatatype QueueBack(Queue *pq);

// 检测是否为空
bool QueueEmpty(Queue *pq);

// 检测元素个数
int QueueSize(Queue *pq);

// 创建二叉树
BTNode *BinaryTreeCreate(BTDataType *a, int n, int *pi);

// 二叉树的销毁
void BinaryTreeDestroy(BTNode **root);

// 二叉树节点个数
int BinaryTreeSize(BTNode *root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode *root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode *root, int k);
// 二叉树查找值为x的节点
BTNode *BinaryTreeFind(BTNode *root, BTDataType x);
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode *root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode *root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode *root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode *root);
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode *root);